//Faster the than light

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define F(i, a, b) for (int i = a; i <= b; i++)
#define R(i, a, b) for (int i = a; i >= b; i--)

#define mk(a, b) make_pair(a, b)
#define inv(x) ksm(x, Mod - 2)
#define mem(a, b) memset(a, b, sizeof a)

#define De(x) cerr << "------------------" << x << "--------------" << endl
#define Debug() cerr << "----------------------------------------" << endl
#define lson(x) x << 1
#define rson(x) x << 1 | 1

const int N = 2e5 + 5, TN = 1e6 + 5, Mod = 998244353, inf = INT_MAX, Inf = LONG_LONG_MAX;
inline int ksm(int a, int b);
inline int read();
string s;
int T = 1, ans = 0, n, m, a[N], head[N], tot, nxt[N], to[N], b[N], c[N];

inline void AddEdge(int u, int v) {
	to[++tot] = v;
	nxt[tot] = head[u];
	head[u] = tot;
}

inline int Calc() {
	int sum=0;
	F(i, 1, n) c[i] = a[i];
	F(i, 1, n){
		sum+=c[b[i]];
		for(int j=head[b[i]];j;j=nxt[j]){ 
		//	cout<<b[i]<<" "<<to[i]<<endl;
			c[to[j]]+=c[b[i]];
		}
	}
//	if(sum==21){
//		F(i,1,n) cout<<b[i]<<" ";
//		puts("");
//	}
	return sum;
}

inline void SA() {
	double T = 1e6;
	int x, y;
	while (T > 1e-12) {
		x = rand() % n + 1, y = rand() % n + 1;
		swap(b[x], b[y]);
		int Ans = Calc();
		int Delta=Ans-ans;
		if(Ans>ans) {ans=Ans;}
		if(exp(Delta)/T<double(rand())/RAND_MAX) swap(b[x],b[y]);
		T *= 0.94;
	}
}

int flower;

inline bool cmp(int x,int y){
	return x>y;
}


inline void NB_SA() {
	double T = 1e6;
	int x, y;
	while (T > 1e-12) {
		x = rand() % n + 1, y = rand() % n + 1;
		if(a[b[x]]>0&&a[b[y]]<0) continue;
		if(a[b[x]]<0&&a[b[y]]>0) continue;
		swap(b[x], b[y]);
		int Ans = Calc();
		int Delta=Ans-ans;
		if(Ans>ans) {ans=Ans;}
		if(exp(Delta)/T<double(rand())/RAND_MAX) swap(b[x],b[y]);
		T *= 0.94;
	}
}

inline void maNb(){
	//Debug();
	sort(a+1,a+n+1,cmp);
	F(i, 1, n) b[i]=i;
	F(i,1,50) NB_SA();
	return;
}


signed main() {
	freopen("light.in","r",stdin);freopen("light.out","w",stdout);
	srand(19260827);
	while (T--) {
		n = read();
		F(i, 1, n) a[i] = read();
		F(i, 1, n - 1) {
			int u, v;
			u = read(), v = read();
			if(u>v) swap(u,v);
			if(u==1) flower++;
			AddEdge(u, v);
			AddEdge(v, u);
		}
		if(flower==n-1){
			maNb();
			cout<<ans;
			return 0;
		}
		F(i, 1, n) b[i] = i;
		F(i, 1, 50) SA();
//		b[1]=4,b[2]=5,b[3]=2,b[4]=1,b[5]=3;
//		Calc();
		cout<<ans;
	}
	return 0;
}
inline int read() {
	int x = 0, f = 1;
	char c = getchar();
	while (c < '0' || c > '9') {
		if (c == '-')
			f *= -1;
		c = getchar();
	}
	while (c <= '9' && c >= '0') {
		x = (x << 3) + (x << 1) + (c ^ 48);
		c = getchar();
	}
	return x * f;
}
inline int ksm(int a, int b) {
	int aa = 1;
	while (b) {
		if (b & 1)
			aa *= a, aa %= Mod;
		a *= a;
		a %= Mod;
		b >>= 1;
	}
	return aa;
}
